'''
z算法
'''
from typing import List

# z[i]: s[i:z[i]] 与 s[0:z[i]] 完全相等
def z_table(s: str) -> List[int]:
    n = len(s)
    z = [0] * n
    z[0] = n
    i, last, r = 1, 1, 1
    while i < n:
        critical_point = i - last
        length = min(z[critical_point], r - i) if r > i else 0
        while i + length < n and s[i + length] == s[length]:
            length += 1
        if i + length > r:
            last, r = i, i + length
        z[i] = length
        i += 1
    return z

# e[i]: s1[i:e[i]] 与 s2[0:e[i]] 完全相等
def e_table(s1: str, s2: str) -> List[int]:
    m, n = len(s1), len(s2)
    e = [0] * m
    z = z_table(s2)
    i, last, r = 0, 0, 0
    while i < m:
        critical_point = i - last
        length = min(z[critical_point], r - i) if r > i else 0
        while i + length < m and length < n and s1[i + length] == s2[length]:
            length += 1
        if i + length > r:
            last, r = i, i + length
        e[i] = length
        i += 1
    return e

def kmp(s1, s2):
    e = e_table(s1, s2)
    n = len(s2)
    for i, length in enumerate(e):
        if length == n:
            return i
    return -1


s1 = 'abaaabbbabaabbabbaba'
s2 = 'abaabb'
print(e_table(s1, s2))
print(kmp(s1, s2))